#include <dbg.h>

#include <cassert>

using namespace std;

class Solution {
public:
    int numberOfSubstrings(string s, int k) {
        int res = 0;
        vector<int> cnt(26, 0);
        int left = 0;
        for (int right = 0; right < s.size(); right++) {
            ++cnt[s[right] - 'a'];
            while (cnt[s[right] - 'a'] >= k) {
                --cnt[s[left] - 'a'];
                ++left;
            }
            res += left;
        }
        return res;
    }
};

int main() {
    Solution s;

    string s1 = "abacb";
    string s2 = "abcde";

    int k1 = 2;
    int k2 = 1;

    assert(s.numberOfSubstrings(s1, k1) == 4);
    assert(s.numberOfSubstrings(s2, k2) == 15);

    return 0;
}